package heap

import C "gitee.com/ljfirst/algo-go-sdk/common/constant"

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/6/27 19:28
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 返回数组中最小的 k 个元素 -> 快排法
 * */
type ReturnKMinByQuickSort struct {
}

func (m *ReturnKMinByQuickSort) ReturnKMin(array []int, k int) []int {
	if array == nil || len(array) < k {
		return nil
	}
	if len(array) == k {
		return array
	}
	m.quickSortDuplex(array, 0, len(array)-1, k)
	return array[:k]
}

func (m *ReturnKMinByQuickSort) quickSortDuplex(array []int, left, right, k int) {
	l, r := left, right
	if left >= right {
		return
	}
	for l < r {
		for l < r && array[r] >= array[left] {
			r--
		}
		for l < r && array[l] <= array[left] {
			l++
		}
		if l < r {
			array[l], array[r] = array[r], array[l]
		}
	}
	array[left], array[l] = array[l], array[left]
	if k == l {
		return
	} else if k < l {
		m.quickSortDuplex(array, left, l-1, k)
	} else {
		m.quickSortDuplex(array, l+1, right, k)
	}
}

func (m *ReturnKMinByQuickSort) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Sort},
		Desc: &C.Desc{
			Name:   "ReturnKMinByHeapSort",
			NameCn: "返回数组中最小的k个元素:快排法",
			Example: map[int]string{
				1: "输入[1,3,2,4,5],K=2,最小的第2个元素是2",
			},
		},
	}
}
